/*
提交链接：https://leetcode.cn/problems/minimum-number-of-days-to-make-m-bouquets/submissions/564511465
1482. 制作 m 束花所需的最少天数-中等
完成日期：2024/9/13
二分搜索
*/

class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        int n = bloomDay.size();
        // 如果花的总数不足以制作 m 束花，则直接返回 -1
        if (m > 0 && k > 0 && n < static_cast<long long>(m) * k) return -1;//防止溢出
        // 二分查找的范围
        int left = 1;
        int right = *max_element(bloomDay.begin(), bloomDay.end());
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canMakeBouquets(bloomDay, m, k, mid)) {
                right = mid; // 尝试更小的天数
            } else {
                left = mid + 1; // 增加天数
            }
        }
        return left;
    }
private:
    bool canMakeBouquets(const vector<int>& bloomDay, int m, int k, int days) {
        int bouquets = 0;
        int flowers = 0;
        for (int bloom : bloomDay) {
            if (bloom <= days) {
                flowers++;
                if (flowers == k) {
                    bouquets++;
                    flowers = 0;
                }
            } else {
                flowers = 0;
            }
        }
        return bouquets >= m;
    }
};